﻿#include<stdlib.h>

//计数排序（适用于数据比较集中）
void CountSort(int* arr, int n)
{
	//找出最大值和最小值来确定开辟数组大小
	int max = arr[0];
	int min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (max < arr[i])
		{
			max = arr[i];
		}
		if (min > arr[i])
		{
			min = arr[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)calloc(sizeof(int), range);

	//统计数组中数组出现的次数
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}

	//取count中的数据存放在原数组中
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}
	}
}